package l07_dynamic_planning.leetCode_120_triangle;

import java.util.ArrayList;
import java.util.List;

/**
 * @author wangxiyue@cyou-inc.com
 * @date 2019-08-16
 * @since 1.0.0
 */
class Solution {
    public static int minimumTotal(List<List<Integer>> triangle) {
        int size = triangle.size();
        int[][] s = new int[size][size];
        int minValue = s[0][0] = triangle.get(0).get(0);
//        int minValue = 0;
        for (int i = 1; i < size; i++) {
            List<Integer> interns = triangle.get(i);
            int size1 = interns.size();
            for (int j = 0; j < size1; j++) {
                if (j == 0) {
                    s[i][j] = s[i - 1][j] + interns.get(j);
                } else if (j == size1 - 1) {
                    s[i][j] = s[i - 1][j - 1] + interns.get(j);
                } else {
                    s[i][j] =
                            Math.min(s[i - 1][j], s[i - 1][j - 1]) + interns.get(j);
                }
                if (i == size - 1) {
                    if (j == 0) {
                        minValue = s[i][j];
                    } else {
                        minValue = Math.min(minValue, s[i][j]);
                    }
                }
            }
        }
        return minValue;
    }

    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList();
        List<Integer> a = new ArrayList();
        a.add(2);
        triangle.add(a);
        List<Integer> b = new ArrayList();
        b.add(3);
        b.add(4);
        triangle.add(b);
        List<Integer> c = new ArrayList();
        c.add(6);
        c.add(5);
        c.add(7);
        triangle.add(b);
        List<Integer> d = new ArrayList();
        d.add(4);
        d.add(1);
        d.add(8);
        d.add(3);
        triangle.add(b);

        System.out.println(minimumTotal(triangle));


    }
}